package com.cloud.code.leetcode;

import java.util.*;

/**
 * 三数之和
 */
public class Demo2 {

    public static void main(String[] args) {
        threeSum(new int[]{-2,1,1,1,2});
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> sets = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int tar = 0 - nums[i];

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum > tar) {
                    right--;
                } else if (sum < tar) {
                    left++;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    sets.add(list);
                    left ++;
                    right --;
                }
            }

        }

        return new ArrayList<>(sets);
    }
}
